In accordance with the various requirements placed upon bandwidth, complexity and cost, various communication systems have formed so as to meet said various requirements.
Single-wire communication networks comprising single wire interfaces (SWI) have become established in the market for not very complex applications, wherein a small number of terminal contacts is desired. Single-wire communication networks support connection to a multitude of slave nodes. In this context, the automotive industry constitutes an important field of application. For example, in automobiles, several simple actuators or sensors are controlled as slave nodes in a hierarchic single-wire communication network by a shared master node.
The master node and the slave nodes are connected to the single-wire connection, or the single wire bus system. New slave nodes may be added to such a single-wire communication network at any time, and connected slave nodes may be removed, or they may temporarily fail or fail for good and possibly be replaced. Each of said slave nodes comprises a memory or other computer-readable medium (e.g., magnetic drive, optical drive, etc.) which has an identifier stored therein by means of which the respective slave node may be identified. The identifier of each node or device is unique, e.g. throughout the world, and is therefore also referred to as a unique ID (identifier). Therefore, the master node is faced with the task of communicating with the individual slave nodes to find out which slave nodes are connected to the single-wire communication network, as well as their IDs, so as to then be able to selectively communicate with them, for example, by means of their unique IDs.
A known search algorithm will be described below, with reference to FIG. 6, which employs a binary search and which is used for determining an ID or an address of a slave node. This binary search algorithm is based on the list of commands briefly explained below:
DISS: starting the search ID algorithm;DIS0: device ID search “0”;DIS1: device ID search “1”;idptr: pointer to an internal ID bit position;active: device status, which may be “True”, i.e. the device is active,or “False”, i.e. the device is deactivated and does not respond to furtherprobes, or search requests, DIS0 or DSI1;uid[x]: array that holds the ID bit stream, “x” indicating the selectionof the desired bit.Assert_IRQ: slave device responds with an interrupt signal IRQ (alsoreferred to as “Interrupt”);Sense_IRQ: when a master node, also referred to as a “HOST”,receives an interrupt signal IRQ from a slave device.
The corresponding search algorithm executed by a slave node or slave device is as follows:
IF command=DISS  idptr=N  active=TrueELSIF command=DIS0 AND active=True  if uid [idptr−−]=0  Assert_IRQELSIF Sense_IRQ  active_FalseELSIF command=DIS1 AND active=True  if uid [idptr−−]=1  Assert_IRQELSIF Sense_IRQ  active=False
In other words, when the slave node receives the command DISS for starting the search, it sets its pointer idptr to the value of N, N designating the number of bits of the ID, e.g. in FIG. 6: N=4, and it enters the active status. When the slave nodes receives the command DIS0 and is in an active status, it decrements the pointer idptr and compares the value stored in its array at the position of the pointer with the value of “0” and transmits an interrupt signal IRQ if this value is equal to the value of “0”. If the value is not the same, the slave node will enter the inactive status. The slave node proceeds in an analog manner when it receives the command DIS1 and is in an active status. In this case, it will decrement the pointer idptr and compare the value of the array defined by the pointer with the value of “1”, and output an interrupt signal IRQ if the value is equal to the value of “1”. Otherwise the slave node proceeds to the inactive state.
By way of example, FIG. 6 shows the sequence of search commands DIS0 and/or DIS1 until a master node finds the addresses “0010” and “0110” (B=binary ID). During this binary search, the master node goes through the binary tree branch by branch in order to find the corresponding ID or address of the slave node. In this context, the master node proceeds in such a manner, for example, that it initially searches for the address “0000”, then for the address “0001”, then for the address “0010”, etc. The master node proceeds position by position, probes, in a first iteration, whether a slave node has the value of “0” at the highest digit, or position, (idptr=3), only this is the case in FIG. 6, i.e. the two slave nodes respond to the first DIS0 with an interrupt, or confirmation, signal IRQ. Subsequently, the master node transmits a second DIS0, to which only the slave node having the ID “0010” responds with the interrupt signal IRQ. Since the second slave node having the address “0110” has a value of “1” at this position, it will deactivate itself and will no longer respond to any of the following search commands of the master node until it is reactivated by the master. The master node now transmits its third DIS0. Since the slave node having the address “0010” has a “1” rather than a “0” at the position UID[1], said slave node will also deactivate itself. Thus, the master node receives no interrupt signal IRQ and thus knows that there is no slave node which has the address “000x”, x being a place holder for one of the two binary values “0” and “1”.
With this, the first search run is completed, and the master node starts a new search run by transmitting the search start command DISS, so that all of the slave nodes will reinitialize themselves, i.e. they will set their internal counters to the value of N=4 and enter the active status. In said second search run, the same command and/or signal exchange as in the first run repeats itself for the first two positions UID[3] and UID[2]. As the third search command, the master node now transmits a DIS1 however, obtains an interrupt signal from the slave node having the address “0010”, said slave node remaining active, at the same time, for continuing the search on this branch or path. As the fourth search signal in this search run, the master node then transmits a DIS0, obtains an interrupt signal from the slave node having the address “0010”, and now that the ID only has four digits, the master node knows that the search has been completed successfully and that a slave node having the address, or ID, “0010”, is connected to the single-wire communication network. The master node proceeds in an analogous manner for all of the other potential IDs until it has found all of the slave nodes.
This approach results in that the binary search will take a very long time if the IDs comprise a large number of bits. When it is assumed that N is the number of ID bits, then the master node may utilize 2N runs if it goes through each branch of the corresponding binary tree having the length N. For example, if N=96 bits, the master node will go through up to 79,228,162,514,264,337,593,543,950,336 branches to find all of the slave nodes which are connected to the single wire line. However, typically, less search runs may be used since only a small number of slave nodes are connected to the single-wire communication network and, thus, over the search, entire sub-trees having no slave node therein need not be considered.